//
// Created by lanlu on 2025/8/5.
//

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int peopleAwareOfSecret(int n, int delay, int forget) {
        // 10^9 + 7
        int MOD = 1e9 + 7;

        // 每个人知道秘密的天数
        vector<int> know_days;
        // 第一天只有一个人知道
        know_days.push_back(1);
        // 从第二天到第n天
        //  i = 2  know_days {1}
        //  i = 3  know_days {1,3}  意思是A在第一天知道秘密 B在第三天知道秘密
        //  i = 4  know_days {1,3,4}
        //  i = 5  know_days {3,4,5}
        //  i = 6  know_days {3,4,5,6,6}
        for (int i = 2; i <= n; i++)
        {
            // 新增知道秘密的人
            vector<int> new_know;

            // 判断是否忘记 以及 是否可以分享
            for (int d : know_days)
            {
                // 计算已经知道秘密的天数
                int days = i - d;
                // 可以分享的情况是 介于delay和forget之间
                if (days >= delay && days < forget)
                {
                    // 需要知道此人是第几天知道秘密的 存储当前的天数
                    new_know.push_back(i);
                }
            }

            // 移除忘记秘密的人
            // 保留还未忘记秘密的人
            vector<int> remaining;
            for (int d : know_days)
            {
                if (i - d < forget)
                {
                    remaining.push_back(d);
                }
            }

            // 把保留的人和新增的人拼接到一起
            remaining.insert(remaining.end(), new_know.begin(), new_know.end());
            know_days = remaining;
        }

        // 最后剩下的就是知道秘密的人
        return know_days.size() % MOD;
    }
};

int main()
{
    Solution s;
    int n = 6;
    int delay = 2;
    int forget = 4;
    int res = s.peopleAwareOfSecret(n, delay, forget);
    cout << res << endl;
    return 0;
}